package fun.coding.leetcode;

public class DistinctSubsequences {
	public static void main(String[] args) {
		DistinctSubsequences ins = new DistinctSubsequences();
		ins.numDistinct("rabbbit", "rabbit");
	}
	
	
	// S is the larger string, T is the smaller one
	// http://www.cnblogs.com/yuzhangcmu/p/4196373.html
	// Normally those type of two string problems could list a matrix, think about DP
	public int numDistinct(String S, String T) {
		if (S == null || T == null) return 0;
		
		if (T.length() > S.length()) return 0;
		
		int row = T.length();
		int col = S.length();
		
		int[][] lookup = new int[row + 1][col + 1];
		
		for (int i = 0; i <= col; i++) {
			lookup[0][i] = 1;
		}
		
		for (int i = 1; i <= row; i++) {
			for (int j = 1; j <= col; j++) {
				// Don't forget to query for i-1, j-1 since we increase the dimension by 1
				lookup[i][j] = lookup[i][j - 1] + (S.charAt(j-1) == T.charAt(i-1) ? lookup[i-1][j-1] : 0);
			}
		}
		//LeetCodeHelpers.printMatrix(lookup);
		return lookup[row][col];
	}
}
